1. Field of the Invention
The present invention relates to a circuit and method for implementing a block cipher algorithm and, more particularly, to a circuit and method for implementing the Advanced Encryption Standard (AES) block cipher algorithm in a system having a plurality of channels.
2. Description of Related Art
The AES block cipher algorithm (hereinafter “AES cipher”) is an iterative cipher algorithm, meaning the data is similarly manipulated a predetermined number of rounds. The AES cipher additionally allows for both a variable block length and variable key length. Specifically, both the block length and key length can be independently set to 128, 192, or 256 bits. The AES cipher also allows for a variable number of rounds (Nr), the total of which may be 10, 12, or 14, and which depends on the block length and key length.
The AES cipher encrypts a block of data by performing 9, 11, or 13 complete round transformations, followed by a final incomplete round transformation. The incomplete round transformation includes one less step than a complete round transformation. The data string that is operated upon during each round is called a “State,” which can be represented as a rectangular array of bytes having four rows and a number of columns (Nb) that varies with the block length. Specifically, the value of Nb is equal to the block length (i.e., 128, 192, or 256) divided by 32, meaning it has a value of either 4, 6, or 8. Each of the complete rounds includes the following four transformations, performed in the following order: (1) ByteSub; (2) ShiftRow; (3) MixColumn; and (4) AddRoundKey. The incomplete round transformation does not include the MixColumn transformation.
Similar to encryption, the AES cipher decrypts data by performing the same number of complete rounds followed by an incomplete round. Because the encryption transformations are invertible, the State of each decryption round is operated on by the inverse of the above-noted transformations. Moreover, the properties of the transformations and inverse transformations allow for symmetry in the encryption and decryption algorithms. In other words, each complete decryption round includes the following inverse transformations, which may be performed in the listed order: (1) InvByteSub; (2) InvShiftRow; (3) InvMixColumn; and (4) InvAddRoundKey. Again, similar to encryption, the incomplete decryption round transformation does not include the InvMixColumn transformation.
As noted above, the initial step in the AES cipher is the ByteSub transformation of the State. In this step, the individual bytes of the State are substituted according to values given in a substitution-box, or S-box. The formula for creating the S-box is disclosed in the Rijndael block cipher specification, the entirety of which is incorporated herein by reference. In summary, what the ByteSub transformation does is replace each byte of the State with its reciprocal in GF(28), multiplied by a bitwise modulo 2 matrix, and XORed with hex ‘63’. The InvByteSub transformation is a byte substitution using the inverse S-box.
During the ShiftRow transformation, the individual rows of the State are shifted over different offsets. Specifically, Row 0 is not shifted, Row 1 is shifted over N1 bytes, Row 2 over N2 bytes, and Row 3 over N3 bytes. The values of N1, N2, and N3 depend on the particular block length. The InvShiftRow transformation is a cyclic shift of Rows 1-3 (again, there is no shift for Row 0) over Nb-N1, Nb-N2, and Nb-N3 bytes, respectively. Again, Nb represents the block length of the State (i.e., 4, 6, or 8).
After the ShiftRow transformation, the MixColumn transformation operates on the State. In the MixColumn transformation, each column of the State is multiplied by the polynomial:c(x)=‘03’x3+‘01’x2+‘01’x+‘02’.In the InvMixColumn transformation, each column of the State is multiplied by the polynomial:d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’,where the polynomial d(x) is defined by the following relationship:(‘03’x3+‘01’x2+‘01’x+‘02’){circle around (×)}d(x)=‘01’.
Finally, in the AddRoundKey transformation, a Round Key is XORed with the State on a bitwise basis. It is noted that AddRoundKey is its own inverse. Thus, the AddRoundKey and InvAddRoundKey transformations are the same.
Each of the Round Keys that are used in each transformation round is derived from an Expanded Key, which is generated from the Cipher Key. More particularly, the Expanded Key is generated by a key expansion process, which may be performed before or during (i.e., “on-the-fly”) the encryption process. Basically, the result of the key expansion process is an Expanded Key whose length is 11, 13, or 15 times that of the original Cipher Key for Nb values of 4, 6, and 8, respectively (e.g., Nb(Nr+1)), and consists of the original Cipher Key, followed by 128-, 192-, or 256-bit blocks consisting of 4-byte words. Each of these 4-byte words is the XOR of the preceding 4-byte word and either the corresponding word in the previous block or a function thereof. Each Round Key is a 128-, 192-, or 256-bit block of the Expanded Key. It is noted that, generation of the Round Keys for the decryption process requires that all of the Round Keys from the encryption process be generated first, since the last Round Key is used first during the decryption process.
The AES cipher, as disclosed in the Rijndael block cipher specification, is a fairly straightforward encryption and decryption scheme. The specification further discloses various hardware implementations and methodologies implemented by the hardware for the scheme. However, the hardware implementations address only single channel implementations, and do not disclose how to implement the AES cipher in a system having a plurality of channels. Additionally, while the specification discloses generating Round Keys on the fly in order to save RAM, it does not disclose how to efficiently perform on the fly Round Key generation for the decryption process. The specification further fails to disclose a hardware implementation for efficiently determining S-box and inverse S-box data substitution values used in the ByteSub and InvByteSub transformations without having to generate the S-box or use a table look-up scheme.
Hence, there is a need in the art for a circuit and method that solves the above-identified problems. Namely, a circuit that implements the AES cipher in system having a plurality of channels, a circuit that efficiently determines AES cipher S-box and inverse S-box data substitution values or a data string, and a method for efficiently generating Round Keys used in decryption rounds of the AES cipher on-the-fly.